/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.TreeMap;

/**
 * @author zhong
 *
 */
public class MatrixCellsinDistanceOrder {
	public int[][] allCellsDistOrder(int R, int C, int r0, int c0) {
		TreeMap<Integer, ArrayList<int[]>> res = new TreeMap<>();
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				int dist = Math.abs(i - r0) + Math.abs(j - c0);
				if (res.containsKey(dist)) {
					res.get(dist).add(new int[] { i, j });
				} else {
					ArrayList<int[]> list = new ArrayList<>();
					list.add(new int[] { i, j });
					res.put(dist, list);
				}
			}
		}
		int[][] rt = new int[R * C][2];
		int i = 0;
		for (Integer dist : res.keySet()) {
			for (int[] js : res.get(dist)) {
				rt[i++] = js;
			}
		}
		return rt;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
